package algorithm.leetcode.I201to400;

/**
 * 多状态dp
 * 比普通的打家劫舍多了一个设定:房屋是连成环状的
 * 也就是0到n-1个屋子和1到n号屋子两种状态中出一个最大值
 *
 * 待优化: dp数组可压缩
 */

// nums:   [1,2,3,1]
// dp_0: [0,1,2,4]
// dp_1:   [0,2,3,3]

public class Q213 {

    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int[] dpBeginZero = new int[nums.length];
        int[] dpBeginOne = new int[nums.length];
        dpBeginZero[0] = 0;
        dpBeginZero[1] = nums[0];
        dpBeginOne[0] = 0;
        dpBeginOne[1] = nums[1];
        int maxVal = Math.max(nums[0], nums[1]);

        for (int i = 1; i < nums.length-1; i++) {
            dpBeginZero[i+1] = Math.max(dpBeginZero[i-1]+nums[i], dpBeginZero[i]);
            dpBeginOne[i+1] = Math.max(dpBeginOne[i-1]+nums[i+1], dpBeginOne[i]);
            maxVal = Math.max(maxVal, Math.max(dpBeginOne[i+1], dpBeginZero[i+1]));
        }
        return maxVal;
    }

    public static void main(String[] args) {
        Q213 q213 = new Q213();
        System.out.println(q213.rob(new int[]{2, 3}));
    }

}
